package com.liunian.algorithmstudy.tree;

public class SortedArrayToBST108 extends TreeNode {

	/**
	 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵平衡二叉搜索树。
	 */

	public TreeNode sortedArrayToBST1(int[] nums) {
		if (nums.length == 0) {
			return null;
		}
		int val = nums[nums.length / 2];
		TreeNode root = new TreeNode(val);
		int[] leftNums = new int[nums.length / 2];
		int[] rightNums = new int[nums.length - (nums.length / 2) - 1];
		for (int i = 0; i < leftNums.length; i++) {
			leftNums[i] = nums[i];
		}
		for (int i = nums.length / 2 + 1; i < nums.length; i++) {
			rightNums[i - (nums.length / 2 + 1)] = nums[i];
		}
		root.left = sortedArrayToBST1(leftNums);
		root.right = sortedArrayToBST1(rightNums);
		return root;
	}

	public TreeNode sortedArrayToBST(int[] nums) {
		return sortedArrayToBST(nums, 0, nums.length - 1);
	}

	private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
		if (left > right) {
			return null;
		}
		int index = (left + right) / 2;
		TreeNode root = new TreeNode(nums[index]);
		TreeNode l = sortedArrayToBST(nums, left, index - 1);
		TreeNode r = sortedArrayToBST(nums, index + 1, right);
		root.left = l;
		root.right = r;
		return root;
	}

}
